package 剑指offer;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class 字形打印二叉树3 {
    public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
	Queue<TreeNode> lQueue = new LinkedList<>();
	Queue<TreeNode> rQueue = new LinkedList<>();
	boolean flag = true;
	ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
	if (pRoot != null) {
	    lQueue.offer(pRoot);
	    	
	    while (!lQueue.isEmpty() ||!rQueue.isEmpty()) {

		
		    ArrayList<Integer> tempList = new ArrayList<>();
		    while (!lQueue.isEmpty()) {
			TreeNode peek = lQueue.remove();
			System.out.print(peek.val + " ");
			tempList.add(peek.val);
			if (peek.left != null) {
			    rQueue.offer(peek.left);

			}
			if (peek.right != null) {
			    rQueue.offer(peek.right);

			} 
			

		    }
		    if (!tempList.isEmpty()) {
			System.out.println();
			lists.add(tempList);
			tempList.clear();
			
		    }
		    while (!rQueue.isEmpty()) {
			TreeNode peek = rQueue.remove();
			System.out.print(peek.val + " ");
			tempList.add(peek.val);
			if (peek.left != null) {
			    lQueue.offer(peek.left);

			}
			if (peek.right != null) {
			    lQueue.offer(peek.right);

			} 
			

		    }
		    if (!tempList.isEmpty()) {
			System.out.println();
			lists.add(tempList);
			tempList.clear();
		    }


		  
		  
		}
	    
	}
	return lists;

    }

    /*
   	 * 	      	8
   	 * 	  6	      10
   	 *   5 	    7      9      11
   	*/
    public static void main(String[] args) {
	// TODO Auto-generated method stub
	TreeNode root = new TreeNode(8);
	root.left = new TreeNode(6);
	root.right = new TreeNode(10);
	root.left.left = new TreeNode(5);
	root.left.right = new TreeNode(7);
	root.right.left = new TreeNode(9);
	root.right.right = new TreeNode(11);
	Print(root);
    }

}
